package 构建前缀信息的技巧_解决子数组相关问题;

import java.io.*;
import java.util.HashMap;

// 返回无序数组中累加和为给定值的最长子数组长度
// 给定一个无序数组arr, 其中元素可正、可负、可0
// 给定一个整数aim
// 求arr所有子数组中累加和为aim的最长子数组长度
// 测试链接 : https://www.nowcoder.com/practice/36fb0fd3c656480c92b569258a1223d5
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下的code，提交时请把类名改成"Main"，可以直接通过
public class Code02_LongestSubarraySumEqualsAim {

    public static int MAXN = 100001;

    public static int[] arr = new int[MAXN];

    // n: 数组的长度     aim: 累加和目标值
    public static int n, aim;

    // key : 某个前缀和
    // value : 这个前缀和最早出现的位置
    public static HashMap<Integer, Integer> map = new HashMap<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer in = new StreamTokenizer(br);
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        while (in.nextToken() != StreamTokenizer.TT_EOF){
            n = (int) in.nval;
            in.nextToken();
            aim = (int) in.nval;
            for(int i = 0; i < n; i++){
                in.nextToken();
                arr[i] = (int) in.nval;
            }
            out.println(compute());
        }
        out.flush();
        out.close();
        br.close();
    }

    public static int compute(){
        map.clear();
        // 重要 : 0这个前缀和，一个数字也没有的时候，就存在了`
        map.put(0, -1);
        int ans = 0;
        for(int i = 0, sum = 0; i < n; i++){
            sum += arr[i];
            // sum-aim如果存在哈希表中，那么用当前位置减去最早出现sum-aim的位置就是，
            // 子数组中累加和为aim的子数组长度
            if(map.containsKey(sum-aim)){
                ans = Math.max(ans, i-map.get(sum-aim));
            }

            if(!map.containsKey(sum)){
                map.put(sum, i);
            }
        }
        return ans;
    }
}
